D - Minimum Width - AtCoder Beginner Contest 319
簡単な方針
解答は最大の単語長$ \max_{i} L_i以上、全てを1行ずつ並べたときの幅$ -1+\sum_{i}(1+L_i)以下にある
疑問
空白込みで単語を計算していた場合(これを計算する関数を$ f'とする)、なぜ最後に1を引く必要があるか？ ---> 空白込みの1文字で入るかどうかを算出している点で、本来の$ f(W)とはずれるため
aは例1の入力系列として、Pythonで$ f'(26)を計算させたら、実際の$ f(26)とはずれていることが確認できる。 https://gyazo.com/82d3c91dcc076359d1f996c92ff7ba4b
元の$ fの計算において、少なくとも一つの行は幅を全て使い切る。 本来の行末には空白は必要がないが、ここでは全ての単語の後に空白を含めて考えてしまっている
なので、その幅を使い切る行においては入り切らず、本来とは異なる結果が出てきてしまう
その点で、幅を1増やした$ f'(W + 1)は正しく$ f(W)を計算してくれる。
行末に当たる全ての単語には必要のない空白が1つ加えられているので、それと加えられた幅1がうまく影響を吸収してくれる。
もっと厳密な言い回しができそう。
知見
通常の二分探索とは違って、begin_W != end_Wだと永遠に終わらない。 // begin_W = mid_W + 1の更新を行なっていればそうでもないのだが、
// 今回はf(W) < aを満たす最小のW(上界)を求めなければならないので、
// このような二分探索をとっている
code:cpp
#define INFO(x) DEBUG(std::cerr << x << std::endl) #define snap(var) DEBUG(std::cerr << "snap " << #var << " = " << (var) << std::endl) using ull = unsigned long long;
/**
* @brief 解答の関数fに相当する
* この関数(数列)Wに対して単調減少するので、
* ある自然数aに対してf(W) = aとなるようなWの二分探索が可能。
*/
ull get_lines_stuffed_words(const std::vector<ull>& L, const ull W){
ull chara_in_line = 0;
ull line_count = 1;
for (const ull word:L){
if (W - chara_in_line < word) {
chara_in_line = 0;
line_count += 1;
}
chara_in_line += word;
}
return line_count;
}
int main(){
int N, M; std::cin >> N >> M;
std::vector<ull> L(N);
// 空白付け足し
for (int i = 0; i < N; i++) { std::cin >> Li; Li++; } ull begin_W = std::ranges::max(L) - 1ull;
ull end_W = std::reduce(L.begin(), L.end());
// 通常の二分探索とは違って、begin_W != end_Wだと永遠に終わらない。
// begin_W = mid_W + 1の更新を行なっていればそうでもないのだが、
// 今回はf(W) < aを満たす最小のW(上界)を求めなければならないので、
// このような二分探索をとっている
while (begin_W + 1 < end_W){
const ull mid_W = std::midpoint(begin_W, end_W);
const ull lines = get_lines_stuffed_words(L, mid_W);
if (lines > M) { begin_W = mid_W; }
else { end_W = mid_W; }
}
std::cout << end_W - 1 << std::endl;
}
解き直し D
全くわからんかったやつ
解を引数にとる関数が単調な関数で表せて